//
// Created by DengLibin on 2019/1/28 0028.
//
#include <stdio.h>
#include <stdlib.h>
/**分治算法：
 * 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，
 * 再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
 * 这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
 * */

/**
 * 汉诺塔问题：盘子编号从上往下递增
 * */
static  int moveNum = 0;//移动次数
/**
 * 移动操作
 * @param i 盘子编号
 * @param c1 柱子1
 * @param c2 柱子2
 */
static void display(int i, char c1, char c2){
        moveNum++;
        printf("%d 号盘子 %c 移到 %c\n", i, c1,c2);
}

/**
 * 汉诺塔 将盘子从A移到C
 * @param num  盘子数量（编号）
 * @param c1  柱子1 A
 * @param c2  柱子2 B
 * @param c3  柱子3 C
 */
static  void move(int num, char c1,char c2, char c3){
    if(num == 1){
        display(num, c1,c3);
    }else{
        move(num-1,c1, c3, c2); // 将上面的num-1个盘子从A移到B（借助C）
        display(num, c1, c3); //将最后一个从A移到C(直接移动)
        move(num-1,c2, c1, c3); //将前num-个从B到C(借助A)
    }
}

int main2(){
    move(4,'A', 'B', 'C');
    printf("移动次数%d\n", moveNum);
    return 0;
}

